package com.zs.letcode.illustration_of_algorithm;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 剑指 Offer 58 - I. 翻转单词顺序
 * 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入: "the sky is blue"
 * 输出:"blue is sky the"
 * 示例 2：
 * <p>
 * 输入: " hello world! "
 * 输出:"world! hello"
 * 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * 示例 3：
 * <p>
 * 输入: "a good  example"
 * 输出:"example good a"
 * 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * <p>
 * 说明：
 * <p>
 * 无空格字符构成一个单词。
 * 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 * 注意：本题与主站 151 题相同：https://leetcode-cn.com/problems/reverse-words-in-a-string/
 * <p>
 * 注意：此题对比原题有改动
 * <p>
 * 相关标签
 * 双指针
 * 字符串
 * <p>
 * Java
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/586ecg/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/28 09:53
 */
public class Chapter61 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.reverseWords("a"));
    }

    private static class Solution {
        public String reverseWords(String s) {
            String leftPart = "", rightPart = "";
            int length = s.length();
            int i = 0, j = length - 1;
            while (i <= j) {
                String left = "";
                while (i <= j && s.charAt(i) == ' ') {
                    i++;
                }
                while (i <= j && s.charAt(i) != ' ') {
                    left += s.charAt(i);
                    i++;
                }
                String right = "";
                while (j > i && s.charAt(j) == ' ') {
                    j--;
                }
                while (j > i && s.charAt(j) != ' ') {
                    right = s.charAt(j) + right;
                    j--;
                }
                leftPart = right.isBlank() ? leftPart : leftPart + right + " ";
                rightPart = left.isBlank() ? rightPart : left + " " + rightPart;
                i++;
                j--;
            }
            return (leftPart + rightPart).trim();
        }

        /**
         * 方法一：双指针
         */
        public String reverseWords1(String s) {
            s = s.trim();
            int j = s.length() - 1, i = j;
            StringBuilder res = new StringBuilder();
            while (i >= 0) {
                while (i >= 0 && s.charAt(i) != ' ') i--;
                res.append(s.substring(i + 1, j + 1) + " ");
                while (i >= 0 && s.charAt(i) == ' ') i--;
                j = i;
            }
            return res.toString().trim();
        }

        /**
         * 方法二：分割 + 倒序
         */
        public String reverseWords2(String s) {
            String[] strs = s.trim().split(" ");
            StringBuilder res = new StringBuilder();
            for (int i = strs.length; i >= 0; i--) {
                if (strs[i].equals("")) continue;
                res.append(strs[i] + " ");
            }
            return res.toString().trim();
        }

        public String reverseWords3(String s) {
            // 除去开头和末尾的空白字符
            s = s.trim();
            // 正则匹配连续的空白字符作为分隔符分割
            List<String> wordList = Arrays.asList(s.split("\\s+"));
            Collections.reverse(wordList);
            return String.join(" ", wordList);
        }

    }
}
